import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-07-03
 * Time: 13:21
 */
//使用双端队列，使得删除的时候效率高一些，得到最大值的时候也只是取队头元素
    //双端队列的用途之一就是实现单调队列
//解决滑动窗口最经典的办法集就是利用双端队列解决问题
    //解题思路：1.队列表示滑动窗口，注意队列存储的是元素的下标，因为这个队列长度不是固定的(先进先出的特性)
    //     2.用单调队列维护滑动窗口(单调递减)
    //     3.队列最左边的元素就是滑动窗口最大值
/*    队列表示滑动窗口
            头尾尾头口诀
            1.头:清理超期元素(清理i-k位置的元素)
               1.1 经过维护的单调队列的长度并不一直保持是k的，所以要清理的元素并不是最左边的元素，我们需要使用下标。
               1.2 所以队列中存储的是一组下标，这组下标对应的元素是单调递减的。
            2.尾:维护单调递减队列(清除队列内<新入队元素的元素)
            3.尾:新元素入队
            4.头:获取滑动窗口最大值(返回头部元素,i>=k -1时)
        注明：i为当前即将入队元素下标，k为滑动窗口大小*/
public class Solution2 {
    public static ArrayList<Integer> maxInWindows(int [] num, int size) {
        if(size> num.length){
            return new ArrayList<>();
        }
        //常用Deque表示双端队列，用linkedlist实现队列，用ArrayDeque实现堆栈
        Deque<Integer> que=new LinkedList<>();
        ArrayList<Integer> ret=new ArrayList<>();
        //创建并维护滑动窗口
        for(int i = 0; i < num.length; i++){
            //1.头：清理超期元素，就是往右移的过程中，清理掉最先进来的下标对应的元素
            if(!que.isEmpty() && que.peek()==i-size){
                que.remove(); //删除的是头部
            }
            //2.尾：维护单调递减队列，就是往右移的过程中，清除队列内<新入队元素的元素
            while(!que.isEmpty() && num[i]>=num[que.peekLast()]){
                que.removeLast();
            }
            //3.尾：新元素入队
            //que.add( i ); //在队尾添加元素
            que.addLast(i); //在队尾添加元素
            //4.头：获取滑动窗口最大值，i>=k-1时
            if(i>=size-1){
                ret.add(num[que.peek()]);  //peek()获取队列头部元素相当于peekFirst，peekLast()获取队列尾部元素
            }
        }
        return ret;
    }
    
    public static void main (String[] args) {
        int[] num = {2,3,4,2,6,2,5,1};
        int size = 3;
        System.out.println(maxInWindows(num,size));
    }
}
